#include "common.h"

int findMaxForm(char** strs, int strsSize, int m, int n);
int findMaxForm2(char** strs, int strsSize, int m, int n);

int main()
{
	char* strs[5] = { "10", "0001", "111001", "1", "0" };
	int strsSize = 5, m = 5, n = 3;
	printf("%d", findMaxForm(strs, strsSize, m, n));
	return 0;
}

int findMaxForm(char** strs, int strsSize, int m, int n)
{
	unsigned char articals[strsSize][2];
	for (int i = 0; i < strsSize; i++) {
		char* str = strs[i];
		unsigned char zero = 0, one = 0;
		for (int j = 0; str[j] != '\0'; j++)
			if (str[j] == '0')
				zero++;
			else
				one++;
		articals[i][0] = zero;
		articals[i][1] = one;
	}

	unsigned short f[m + 1][n + 1];
	memset(f, 0, sizeof(f));
	for (int k = 0; k < strsSize; k++) {
		unsigned char zero = articals[k][0], one = articals[k][1];
		for (int i = m; i >= zero; i--)
			for (int j = n; j >= one; j--)
				if (f[i][j] < f[i - zero][j - one] + 1)
					f[i][j] = f[i - zero][j - one] + 1;
	}

	return f[m][n];
}

// 尝试优化 ——————————————————————————————————————————————————
int findMaxForm2(char** strs, int strsSize, int m, int n)
{
	unsigned char articals[strsSize][2];
	for (int i = 0; i < strsSize; i++) {
		char* str = strs[i];
		unsigned char zero = 0, one = 0;
		for (int j = 0; str[j] != '\0'; j++)
			if (str[j] == '0')
				zero++;
			else
				one++;
		articals[i][0] = zero;
		articals[i][1] = one;
	}

	unsigned short f[m + 1][n + 1];
	memset(f, 0, sizeof(f));
	for (int k = 0; k < strsSize; k++) {
		unsigned char zero = articals[k][0], one = articals[k][1];
		for (int i = m; i >= zero; i--)
			for (int j = n; j >= one; j--)
				if (f[i][j] < f[i - zero][j - one] + 1)
					f[i][j] = f[i - zero][j - one] + 1;
	}

	int res = f[m][n];
	free(f);
	free(articals);
	return f[m][n];
}
